// https://www.lintcode.com/problem/unique-paths-ii/description

class Solution {
public:
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */
    // int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
    //     int n = obstacleGrid.size();
    //     int m = obstacleGrid[0].size();
    //     vector<vector<int>> res(n, vector<int>(m, 0));
    //     // res[0][0] = 1; 初始也要根据格子的情况！！！。。。
    //     if (obstacleGrid[0][0] == 1 || obstacleGrid[n - 1][m - 1] == 1) return 0;
    //     res[0][0] = 1;
    //     for (int i = 1; i < n; ++i)
    //     {
    //         if (obstacleGrid[i][0] == 1) 
    //             res[i][0] = 0;
    //         else
    //             res[i][0] = res[i - 1][0];
    //     }
    //     for (int i = 1; i < m; ++i)
    //     {
    //         if (obstacleGrid[0][i] == 1)
    //             res[0][i] = 0;
    //         else
    //             res[0][i] = res[0][i - 1];
    //     }
    //     for (int i = 1; i < n; ++i)
    //     {
    //         for (int j = 1; j < m; ++j)
    //         {
    //             if (obstacleGrid[i][j] == 1) res[i][j] = 0;
    //             else res[i][j] = res[i - 1][j] + res[i][j - 1];
    //             cout << i << " " << j << " " << res[i][j] << endl;
    //         }
    //     }
    //     return res[n - 1][m - 1];
    // }
    
    // 写法二：
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid) {
        if (obstacleGrid.size() == 0) return 0;
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> res(m, vector<int>(n, 0));
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (obstacleGrid[i][j] == 1) {
                    res[i][j] = 0;
                    continue;
                }
                if (i == 0 && j == 0) 
                {
                    res[i][j] = 1;
                    continue;
                }
                if (i > 0) res[i][j] += res[i - 1][j];
                if (j > 0) res[i][j] += res[i][j - 1];
            }
        }
        return res[m - 1][n - 1];
    }
};


// https://leetcode.cn/problems/unique-paths-ii/

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid.empty()) return 0;
        int m = obstacleGrid.size();
        int n = obstacleGrid[0].size();
        vector<vector<int>> rec(m, vector<int>(n));
        rec[0][0] = 1;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (obstacleGrid[i][j] == 1) rec[i][j] = 0;
                else {
                    if (i >= 1) rec[i][j] += rec[i - 1][j];
                    if (j >= 1) rec[i][j] += rec[i][j - 1];
                }
            }
        }
        return rec[m - 1][n - 1];
    }
};